package leetcode.editor.cn;
//Java：二分查找
public class BinarySearch{
    public static void main(String[] args) {
        Solution solution = new BinarySearch().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 因为数组是有序的，并且不重复，所以查找一个值可以用二分法。
     * 二分法有两种：左闭右闭，左闭右开。即right对应的值是否在nums内。
     * 两种方式的不同有两处：
     * 1、对于左闭右开，while中left==right是无意义的。因为right对应的nums不可能在其内。
     * 2、对于左闭右开，如果target<nums[mid]的时候，应该是去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
     * <p>
     * 问题一：为什么while循环中，如果left <= right 的时候，最后的right需要mid-1;而left < right的时候，需要result=mid;
     * 答：因为while循环中是否等于right决定对是否对right下标对应的数值进行检查。
     * 1、当left<=right的时候，说明是左闭右闭。需要对nums[right]进行检查。检查后说明此时的nums[right]的值已经明确小于target，所以下次检查需要跳过right这个下标，即right=mid-1;
     * 2、当left<right的时候，说明是左闭右开。这时的right极限值时 nums.length，对应的数值不存在，所以每次都不需要对result下标数据进行检查。
     */
     class Solution {

        /**
         * 左闭右闭
         * @param nums   数组
         * @param target 目标值
         * @return 目标值下标
         */
/*        public int search(int[] nums, int target) {
            if (target < nums[0] || target > nums[nums.length - 1]) {
                return -1;
            }
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (target == nums[mid]) {
                    return mid;
                } else if (target > nums[mid]) {
                    left = mid + 1;
                } else if (target < nums[mid]) {
                    right = mid - 1;
                }
            }
            return -1;
        }*/

        /**
         * 左闭右开
         * @param nums   数组
         * @param target 目标值
         * @return 目标值下标
         */
        public int search(int[] nums, int target) {
            if (target < nums[0] || target > nums[nums.length - 1]) {
                return -1;
            }
            int left = 0, right = nums.length;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (target == nums[mid]) {
                    return mid;
                } else if (target > nums[mid]) {
                    left = mid + 1;
                } else if (target < nums[mid]) {
                    right = mid;
                }
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}